#include <iostream>
#include <vector>
#include <algorithm>
#include <sys/time.h>

using namespace std;


int maxArea(vector<int>& height) 
{
  int n = height.size();
  if(n<2)
    return 0;
  int ret=0;
  int area;
  int h=0;
  int mi=0,mj=0;
  for(int i=0;i<n-1;++i)
    for(int j=n-1;j>i;--j)
    {
      if(height[j]<height[i])
      {
        if( (height[j]*(j-i)) >ret )
        {
          ret = height[j]*(j-i);
          mi=i;
          mj=j;
        }
      }
      else
      {
        area = height[i]*(j-i);  //this must be the max area in current inner loop
        if(area>ret)
        {
          ret = area;
          mi=i;
          mj=j;

        }
        break;

      }

    }
  cout <<"i,j:"<<mi<<","<<mj<<endl;
  return ret;

}


int main(int argc,char *argv[])
{


  vector<int> height1={2,3,1,2,1,1};

  vector<int> height2;
  for(int i=15000;i>0;--i)
    height2.push_back(i);

  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);
  cout<<maxArea(height1 )<<endl;
  int time2 = gettimeofday(&tv2,&tz);
  cout << "height 1 time consuming:" << tv2.tv_usec - tv1.tv_usec <<"us"<< endl;

  gettimeofday(&tv1,&tz);
  cout<<maxArea(height2 )<<endl;
  gettimeofday(&tv2,&tz);
  cout << "height2 time consuming:" << tv2.tv_usec - tv1.tv_usec <<"us"<< endl;




  return 0;
}
